package com.example.leetcode.leetcode;

/**
 * @author zhuhaitao
 * @email zhuhaitao@imoran.net
 * @date 2020/9/16 9:30 上午
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution226 {

    public static TreeNode invertTree(TreeNode root) {
        reverse(root);
        return root;
    }

    public static void reverse(TreeNode root) {
        if (null == root) {
            return;
        }
        TreeNode t = root.right;
        root.right = root.left;
        root.left = t;
        if (null != root.right) {
            reverse(root.right);
        }
        if (null != root.left) {
            reverse(root.left);
        }
    }

    // 先序遍历

    public static void preorder(TreeNode root) {
        if (null == root) {
            return;
        }
        System.out.print(root.val);
        if (null != root.left) {
            preorder(root.left);
        }
        if (null != root.right) {
            preorder(root.right);
        }
    }

    // 中序遍历
    public static void medium(TreeNode root) {
        if (null == root) {
            return;
        }
        if (null != root.left){
            medium(root.left);
        }
        System.out.print(root.val);
        if (null != root.right) {
            medium(root.left);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        TreeNode rl = new TreeNode(2);
        TreeNode rr = new TreeNode(7);
        root.left = rl;
        root.right = rr;
        TreeNode rll = new TreeNode(1);
        TreeNode rlr = new TreeNode(3);
        rl.left = rll;
        rl.right = rlr;
        TreeNode rrl = new TreeNode(6);
        TreeNode rrr = new TreeNode(9);
        rr.left = rrl;
        rr.right = rrr;
        preorder(root);
        invertTree(root);
        System.out.println();
        preorder(root);
    }
}
